@Part[Intro, Root = "CLM.MSS"]
@Comment{Chapter of Common Lisp Manual.  Copyright 1984 Guy L. Steele Jr.⎇

@MyChapter[Introduction]

@clisp is a new dialect of @xlisp, a
successor to @maclisp @Cite[MOONUAL, PITMANUAL], influenced strongly by @lmlisp
@Cite[BLUE-LISPM, GREEN-LISPM] and also to some extent by @scheme
@Cite[SCHEME-REVISED-REPORT] and @interlisp @Cite[INTERLISP].

@Section[Purpose]

@clisp is intended to meet these goals:
@Begin[Description]
@i[Commonality].@\@clisp originated in an attempt to focus the work
of several implementation groups, each of which was constructing successor
implementations of @maclisp for different computers.  These
implementations had begun to diverge because of the differences in the
implementation environments: microcoded personal computers (@lmlisp,
@slisp), commercial timeshared computers (@newlisp), and supercomputers
(@s1lisp).  While the differences among the several implementation
environments of necessity will continue to force
certain incompatibilities among the
implementations, @clisp serves as a common dialect to
which each implementation makes any necessary extensions.

@i[Portability].@\@clisp intentionally excludes features
that cannot be implemented easily on a broad class of machines.
On the one hand, features that are difficult or expensive
to implement on hardware without special microcode are avoided
or provided in a more abstract and efficiently implementable form.
(Examples of this are the invisible forwarding pointers
and locatives of @lmlisp.  Some of the problems that they solve
are addressed in different ways in @clisp.)
On the other hand, features that are useful only on certain ``ordinary''
or ``commercial'' processors are avoided or made optional.  (An example of
this is the type declaration facility, which is useful in some
implementations and completely ignored in others.  Type declarations are
completely optional and for correct programs
affect only efficiency, not semantics.)
@clisp is designed to make it easy to write programs
that depend as little as possible on machine-specific
characteristics, such as word length, while allowing some variety of
implementation techniques.

@i[Consistency].@\Most @xlisp implementations are internally inconsistent
in that by default the interpreter and compiler may assign different
semantics to correct programs.
This semantic difference stems primarily from the fact
that the interpreter assumes all variables to be dynamically scoped,
whereas the compiler assumes all variables to be local unless explicitly
directed otherwise.  This difference has been the usual practice in @xlisp
for the sake of convenience
and efficiency, but can lead to very subtle bugs.  The definition of
@clisp avoids such anomalies by explicitly requiring the interpreter
and compiler to impose identical semantics on correct programs
so far as possible.

@i[Power].@\@clisp is a descendant of @maclisp, which has traditionally
placed emphasis on providing system-building tools.
Such tools may in turn be used to build the user-level packages
such as @interlisp provides; these packages are not, however, part
of the @clisp core specification.  It is expected such packages will
be built on top of the @clisp core.

@Begin[Multiple]
@i[Expressiveness].@\@clisp culls what
experience has shown to be the most useful and understandable constructs
from not only @maclisp, but also
@interlisp, other @xlisp dialects, and other programming languages.
Constructs judged to be awkward or less useful have been
excluded.   (An example is the @f[store] construct of @maclisp.)
@End[Multiple]

@i[Compatibility].@\Unless there is a good reason to the contrary,
@clisp strives to be compatible with @lmlisp, @maclisp, and
@interlisp, roughly in that order.

@i[Efficiency].@\@clisp has a number of features designed to
facilitate the production of high-quality compiled code in those
implementations whose developers
care to invest effort in an optimizing compiler.
One implementation of @clisp, namely @s1lisp, already has a compiler
that produces code for numerical computations that is competitive
in execution speed to that produced by a @fortran compiler @Cite[S1-COMPILER].
The @s1lisp compiler
extends the work done in @maclisp to produce extremely efficient
numerical code @Cite[MACLISP-BEATS-FORTRAN].

@i[Stability].@\It is intended that @clisp
will change only slowly and with due deliberation.  The various dialects
that are supersets of @clisp may serve as laboratories within which to
test language extensions, but such extensions will be added to
@clisp only after careful examination and experimentation.
@End[Description]
The goals of @clisp are thus very close to those of @stdlisp
@cite[STANDARD-LISP-REPORT] and @psl @cite[PSL-MANUAL].
@clisp differs from @stdlisp
primarily in incorporating more features, including a
richer and more complicated set of data types and more complex
control structures.

This book is intended to be a language specification
rather than an implementation specification
(although implementation notes are scattered throughout the text).
It defines a set of
standard language concepts and constructs that may be used
for communication of data structures and algorithms in the @clisp
dialect.  This set of concepts
and constructs is sometimes referred to as the ``core @clisp language''
because it contains conceptually necessary or important features.
It is not necessarily implementationally minimal.
While many features could be defined in terms of others
by writing @xlisp code, and indeed may be implemented that way,
it was felt that these features should be conceptually primitive
so that there might be agreement among all users as to their usage.
(For example, bignums and rational numbers could be implemented as
@xlisp code given operations on fixnums.  However, it is important
to the conceptual integrity of the language that they be regarded
by the user as primitive, and they are useful enough to warrant
a standard definition.)

For the most part, this book defines a programming language, not a
programming environment.  A few interfaces are defined for
invoking such standard programming tools as a compiler, an editor,
a program trace facility, and a debugger, but very little is said
about their nature or operation.  It is expected that one or more
extensive programming environments will be built using @clisp as a
foundation, and will be documented separately.


@Section[Notational Conventions]

A number of special notational conventions are used throughout this book.

@Subsection[Decimal Numbers]

All numbers in this book are in decimal notation unless
there is an explicit indication to the contrary.
(Decimal notation is normally taken for granted, of course.
Unfortunately, for certain other dialects of @xlisp, @maclisp in particular,
the default notation for numbers is octal (base 8) rather than decimal,
and so the use of decimal notation for describing @clisp is,
taken in its historical context, a bit unusual!)

@Subsection[Nil, False, and the Empty List]

In @clisp, as in most @xlisp dialects, the symbol @Conref[nil]
is used to represent both the empty list and the ``false'' value
for Boolean tests.  An empty list may, of course, also be written
@f[()]; this normally denotes the same object as @f[nil].
(It is possible, by extremely perverse manipulation of the package system,
to cause the sequence of letters @f[nil] to be recognized
not as the symbol that represents the empty list but as another
symbol with the same name.  This obscure possibility will be ignored
in this manual.)
These two notations may be used interchangeably as far as the @xlisp
system is concerned.  However, as a matter of style,
this manual
uses the notation @empty@; when it is desirable to emphasize
the use of an empty list, and uses the notation @false@;
when it is desirable to emphasize the use of the Boolean ``false.''
The notation @f['nil] (note the explicit quotation mark) is used to emphasize
the use of a symbol.
For example:
@lisp
@tabdivide[2]
(defun three () 3)@\;@r[Emphasize empty parameter list.]
(append '@empty '@empty) @EV @empty@\;@r[Emphasize use of empty lists]
(not @false) @EV @true@\;@r[Emphasize use as Boolean ``false'']
(get '@nil 'color)@\;@r[Emphasize use as a symbol]
@Endlisp

Any data object other than @false is construed to be Boolean
``not false,'' that is, ``true.''  The symbol @true is conventionally
used to mean ``true'' when no other value is more appropriate.
When a function is said to ``return @i[false]'' or to ``be @i[false]''
in some circumstance, this means that it returns @false.
However, when a function is said to ``return @i[true]'' or to ``be @i[true]''
in some circumstance, this means that it returns some value other
than @false, but not necessarily @true.

@Subsection[Evaluation, Expansion, and Equivalence]

Execution of code in @xlisp is called @i[evaluation] because executing a
piece of code normally results in a data object called the @i[value]
produced by the code.  The symbol @EV is used in examples to
indicate evaluation.
For example:
@Lisp
(+ 4 5) @EV 9
@Endlisp
means ``the result of evaluating the code @f[(+ 4 5)] is (or would be,
or would have been) @f[9].'' 

The symbol @EX is used in examples to indicate macro expansion.
For example:
@Lisp
(push x v) @EX (setf v (cons x v))
@Endlisp
means ``the result of expanding the macro-call form @f[(push x v)]
is @f[(setf v (cons x v))].''  This implies that the two pieces
of code do the same thing; the second piece of code is
the definition of what the first does.

The symbol @EQ is used in examples to indicate code equivalence.
For example:
@Lisp
(gcd x (gcd y z)) @EQ (gcd (gcd x y) z)
@Endlisp
means ``the value and effects of evaluating the form
@f[(gcd x (gcd y z))] are always the same as the value
and effects of
@f[(gcd (gcd x y) z)] for any values of the
variables @f[x], @f[y], and @f[z].''
This implies that the two pieces
of code do the same thing; however, neither directly defines
the other in the way macro expansion does.

@Subsection[Errors]

When this manual specifies that it ``is an error'' for some situation
to occur, this means that:
@Begin[Itemize, spread .5]
No valid @clisp program should cause this situation to occur.

If this situation occurs, the effects and results are completely
undefined as far as adherence to the @clisp specification is concerned.

No @clisp implementation is required to detect such an error.
Of course, implementors are encouraged to provide for detection
of such errors wherever reasonable.
@End[Itemize]
This is not to say that some particular implementation might not define
the effects and results for such a situation; the point is that no program
conforming to the @clisp specification may correctly depend on such
effects or results.

On the other hand, if it is specified in this manual that in some situation
``an error is @i[signalled],'' this means that:
@Begin[Itemize,spread .5]
If this situation occurs, an error will be signalled
(see @Funref[error] and @Funref[cerror]).

Valid @clisp programs may rely on the fact that an error will be signalled.

Every @clisp implementation is required to detect such an error.
@End[Itemize]

In places where it is stated that so-and-so ``must'' or ``must not''
or ``may not''  be the case, then it ``is an error'' if the stated requirement
is not met.  For example, if an argument ``must be a symbol,'' then it
``is an error'' if the argument is not a symbol.  In all cases where
an error is to be @i[signalled], the word ``signalled'' is always used
explicitly in this manual.

@Begin[Table]
@Mline[]
@Caption[Sample Function Description]
@Tag[Sample-Function-Description]
@Defun[Fun {sample-function⎇, Args {@i[arg1] @i[arg2] @optional @i[arg3] @i[arg4]⎇]
The function @f[sample-function] adds together @i[arg1] and @i[arg2], and
then multiplies the result by @i[arg3].  If @i[arg3] is not provided or
is @nil, the multiplication isn't done.  @f[sample-function] then returns
a list whose first element is this result and whose second element is
@i[arg4] (which defaults to the symbol @f[foo]).
For example:
@lisp
(sample-function 3 4) @EV (7 foo)
(sample-function 1 2 2 'bar) @EV (6 bar)
@Endlisp
In general,
@f[(sample-function @i[x] @i[y])] @EQ @f[(list (+ @i[x] @i[y]) 'foo)].
@Enddefun
@Mline[]
@Caption[Sample Variable Description]
@Tag[Sample-Variable-Description]
@Defvar[Var {sample-variable⎇]
The variable @var[sample-variable] specifies how many times
the special form @f[sample-special-form] should iterate.
The value should always be a non-negative integer or @nil
(which means iterate indefinitely many times).  The initial value is @f[0].
@Enddefvar
@Mline[]
@Caption[Sample Constant Description]
@Tag[Sample-Constant-Description]
@Defcon[Var {sample-constant⎇]
The named constant @f[sample-constant] has as its value
the height of the terminal screen in furlongs times
the base-2 logarithm of the implementation's total disk capacity in bytes,
as a floating-point number.
@Enddefcon
@Mline[]
@End[Table]

@begin[Table]
@mline[]
@Caption[Sample Special Form Description]
@Tag[Sample-Special-Form-Description]
@Defspec[Fun {sample-special-form⎇, Args {@Mopt<@i[name]> (@Mstar<@i[var]>) @Mplus<@i[form]>⎇]
This evaluates each form in sequence as an implicit @f[progn], and does this
as many times as specified by
the global variable @var[sample-variable].  Each variable @i[var] is bound
and initialized to @f[43] before the first iteration, and unbound after
the last iteration.
The name @i[name], if supplied, may be used in a @Specref[return-from] form
to exit from the loop prematurely.  If the loop ends normally,
@f[sample-special-form] returns @nil.
For example:
@lisp
(setq @var[sample-variable] 3)
(sample-special-form @empty @i[form1] @i[form2])
@Endlisp
This evaluates @i[form1], @i[form2], @i[form1], @i[form2], @i[form1], @i[form2]
in that order.
@Enddefspec
@mline[]
@Caption[Sample Macro Description]
@Tag[Sample-Macro-Description]
@Defmac[Fun {sample-macro⎇, Args {@i[var] @Mstar<@i[tag] @mor @i[statement]>⎇]
This evaluates the statements as a @f[prog] body,
with the variable @i[var] bound to @f[43].
@Lisp
(sample-macro x (return (+ x x))) @EV 86
(sample-macro @i[var] . @i[body]) @EX (prog ((@i[var] 43)) . @i[body])
@Endlisp
@Enddefmac
@Mline[]
@End[Table]

@Subsection[Descriptions of Functions and Other Entities]

Functions, variables, named constants, special forms, and macros are described
using a distinctive typographical format.
Definition @Ref[Sample-Function-Description] illustrates the manner
in which @clisp functions are documented.
The first line specifies the name of the function,
the manner in which it accepts arguments,
and the fact that it is a function.
If the function takes many arguments, then the names of the arguments
may spill across two or three lines.
The paragraphs following this standard header
explain the definition and uses of the function and often
present examples or related functions.

Sometimes two or more related functions are explained in a single
combined description.  In this situation the headers for all the
functions appear together, followed by the combined description.

In general, actual code (including actual names of functions)
appears in this typeface: @f[(cons a b)].
Names that stand for pieces of code (metavariables) are written in
@i[italics].  In a function description, the names of the parameters appear
in italics for expository purposes.  The word @f[&optional] in the
list of parameters indicates that all arguments past that point are
optional; the default values for the parameters are described in the
text.  Parameter lists may also contain @rest@;, indicating that an
indefinite number of arguments may appear, or @key@;, indicating
that keyword arguments are accepted.
(The @optional/@rest/@key
syntax is actually used in @clisp function definitions for these purposes.)

Definition @Ref[Sample-Variable-Description] illustrates the manner in
which a global variable is documented.  The first line specifies the
name of the variable and the fact that it is a variable.
Purely as a matter of convention, all global variables used
by @clisp have names beginning and ending with an asterisk.

Definition @Ref[Sample-Constant-Description] illustrates the manner in
which a named constant is documented.  The first line specifies the
name of the constant and the fact that it is a constant.
(A constant is just like a global variable, except that it is
an error ever to alter its value or to bind it to a new value.)

Definitions @Ref[Sample-Special-Form-Description]
and @Ref[Sample-Macro-Description] illustrate the documentation
of special forms and macros, which are closely related in purpose.
These are very different from functions.
Functions are called according to a single, specific, consistent syntax;
the @optional/@rest/@key syntax specifies how the function uses its arguments
internally, but does not affect the syntax of a call.
In contrast, each special form or macro can have its own idiosyncratic syntax.
It is by special forms and macros that the syntax of @clisp is defined
and extended.

In the description of a special form or macro, an italicized word names a
corresponding part of the form that invokes the special form or macro.
Parentheses stand for themselves, and should be
written as such when invoking the special form or macro.
Brackets, braces, stars, plus signs, and vertical bars are metasyntactic
marks.
Brackets,
@lbracket@; and @rbracket@;, indicate that what they enclose is optional
(may appear zero times or one time in that place); the square
brackets should not be written in code.
Braces, @lbrace@; and @rbrace@;, simply parenthesize what they enclose,
but may be followed by a star, *, or a plus sign, +;
a star indicates that what the braces enclose may appear any number of times
(including zero, that is, not at all), whereas a plus sign indicates
that what the braces enclose may appear any non-zero number of times
(that is, must appear at least once).  Within braces or brackets,
a vertical bar, |, separates mutually exclusive choices.
In summary, the notation @Mstar<@i[x]> means zero or more occurrences
of @i[x], the notation @Mplus<@i[x]> means one or more occurrences
of @i[x], and the notation @mopt<@i[x]> means zero or one occurrences
of @i[x].  These notations are also used for syntactic
descriptions expressed as @c[bnf]-like productions, as
in Definition @Ref[NUMBER-SYNTAX-TABLE].

In the last example in Definition @Ref[Sample-Macro-Description], notice the
use of dot notation.  The dot appearing in the expression
@f[(sample-macro @i[var] . @i[body])] means that the name @i[body] stands
for a list of forms, not just a single form, at the end of a list.  This
notation is often used in examples.
@Blankspace[2 lines]

@subsection[The Lisp Reader]

The term ``@xLisp reader'' refers not to you, the reader of this manual,
nor to some person reading @xlisp code, but specifically
to a @xlisp procedure, namely the function @Funref[read],
that reads characters from an input stream and interprets them by parsing
as representations of @xlisp objects.

@subsection[Overview of Syntax]

Certain characters are used in special ways in the syntax of @clisp.
The complete syntax is explained in detail in chapter @Ref[IO],
but a quick summary here may be useful:
@Begin[DenseDescription, Leftmargin +.3 in, Indent -.3 in]
@f[(]@\A left parenthesis begins a list of items.  The list may
contain any number of items, including zero.  Lists may be nested.
For example, @f[(cons (car x) (cdr y))] is a list of three things,
of which the last two are themselves lists.

@f[)]@\A right parenthesis ends a list of items.

@f[']@\An accent acute (also called single quote or apostrophe)
followed by an expression @i[form]
is an abbreviation for @f[(quote @i[form])].  Thus @f['foo] means
@f[(quote foo)] and @f['(cons 'a 'b)] means @f[(quote (cons (quote a) (quote b)))].

@f[;]@\Semicolon is the comment character.  It and all characters up to the
end of the line are discarded.

@f["]@\Double quotes surround character strings:
@f["This is a thirty-nine character string."].

@f[\]@\Backslash is an escape character.  It causes the
next character to be treated as a letter rather than for its usual
syntactic purpose.  For example, @f[A\(B] denotes a symbol whose name is
consists of the three characters @f[A], @f[(], and @f[B].
Similarly, @f["\""] denotes a character string containing one character,
a double quote, because the first and third double quotes serve to
delimit the string, and the second double quote serves as the contents
of the string.  The backslash causes the second double quote to
be taken literally, and prevents it from
being interpreted as the terminating delimiter of the string.

@f[|]@\Vertical bars are used in pairs
to surround the name (or part of the name) of a symbol that has
many special characters in it.  It is roughly equivalent to putting a
backslash in front of every character so surrounded.  For example,
@f[|A(B)|], @f[A|(|B|)|], and @f[A\(B\)] all mean the symbol whose name
consists of the four characters @f[A], @f[(], @f[B], and @f[)].

@f[#]@\The number sign signals the beginning of a complicated
syntactic structure.
The next character designates the precise syntax to follow.
For example, @f[#o105] means 105@-[8] (105 in octal notation);
@f[#x105] means 105@-[16] (105 in hexadecimal notation);
@f[#b1011] means 1011@-[2] (1011 in binary notation);
@f[#\L] denotes a character object for the character @f[L]; and
@f[#(a b c)] denotes a vector of three elements @f[a], @f[b], and @f[c].
A particularly important case is that @f[#'@i[fn]] means @f[(function @i[fn])],
in a manner analogous to @f['@i[form]] meaning @f[(quote @i[form])].

@f[`]@\Accent grave (``backquote'') signals that the next expression
is a template that may contain commas.  The backquote syntax
represents a program that will construct a data structure
according to the template.

@f[,]@\Commas are used within the backquote syntax.

@f[:]@\Colon is used to indicate which package a symbol belongs to.
For example, @f[network:reset] denotes the symbol named @f[reset]
in the package named @f[network].  A leading colon indicates a @i[keyword],
a symbol that always evaluates to itself.
The colon character is not actually part of the print name
of the symbol.
This is all explained in chapter @Ref[XPACK]; until you read
that, just keep in mind that a symbol notated with a leading colon
is in effect a constant that evaluates to itself.
@End[DenseDescription]

Brackets, braces, question mark, and exclamation point
(that is, @f{@lbracket⎇, @f{@rbracket⎇, @f[@lbrace], @f[@rbrace], @f[?],
and @f[!]) are not used for any purpose in standard @clisp syntax.
These characters are explicitly reserved to the user, primarily
for use as @i[macro characters] for user-defined lexical syntax extensions.
See section @ref[MACRO-CHARACTERS-SECTION].

All code in this manual is written using lowercase letters.
@clisp is generally insensitive to the case in which code
is written.  Internally, names of symbols are ordinarily
converted to and stored in uppercase form.
There are ways to force case conversion on output if desired;
see @varref[print-case].
In this manual, wherever an interactive exchange between a user
and the @xlisp system is shown, the input is exhibited with lowercase
letters and the output with uppercase letters.